package Algorithm.interview;

/**
 * @Author self
 * @Date 2024/9/12 20:29
 * @Describe 实现一个简单的算法来检查给定字符串中小括号 () 和大括号 {} 是否匹配。
 * 思路是使用 栈 来追踪开放的括号，当遇到闭合括号时，检查它是否能和栈顶的开放括号匹配。
 */
import java.util.Stack;

public class BracketMatcher {
    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();

        for (char c : s.toCharArray()) {
            // 如果是开放括号，入栈
            if (c == '(' || c == '{') {
                stack.push(c);
            }
            // 如果是闭合括号，检查栈顶是否匹配
            else if (c == ')' || c == '}') {
                if (stack.isEmpty()) {
                    return false;  // 闭合括号没有对应的开放括号
                }
                char top = stack.pop();
                // 检查是否匹配
                if ((c == ')' && top != '(') || (c == '}' && top != '{')) {
                    return false;
                }
            }
        }

        // 栈为空，说明所有括号匹配
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        String test1 = "(){}";  // True
        String test2 = "({})";  // True
        String test3 = "({)}";  // False
        String test4 = "({})("; // False

        System.out.println(isValid(test1)); // 输出: true
        System.out.println(isValid(test2)); // 输出: true
        System.out.println(isValid(test3)); // 输出: false
        System.out.println(isValid(test4)); // 输出: false
    }
}

